The fundamentals of the MRI experiment are well known. Briefly (and hopefully without undue oversimplification), in a typical MRI system an object 10 (see FIG. 2) to be imaged (e.g., a portion of the human body) is placed in an external static magnetic field gradient. Protons within the object tend to align their spins in accordance with the magnetic field direction. The object is excited by one or more RF excitation pulses of appropriate frequency, timings and durations (as one example, so-called "spin-echo" type pulse sequences may be used). The RF excitation pulses generated at the Larmour frequency cause the protons to precess their spins. When each RF pulse is switched off, the nuclei precess back toward their equilibrium position and in this relaxation process emit an NMR response that can be detected by an RF receiver.
As is well known, different pulse sequences can be used to obtain different results. A pulse sequence generator (hereafter "sequencer") portion of the system (e.g., often a high-speed hardware state machine based on a bit slice processor architecture) provides the sequence of control signals that controls the operation of the RF transmitter(s), RF receiver(s) and gradient magnet(s). The sequencer must reliably provide a high degree of flexibility (e.g., to provide generation of different desired pulse sequences) as well as adequate time resolution and other important features.
The following is a non-exhaustive listing of possibly representative prior patents and articles relating to NMR sequencers:
As described in some of the documents listed above, a sequencer may comprise a microcoded sequential state machine, with each different state providing different output control signals to control different portions of the NMR equipment (e.g., RF transmitter and receiver, gradient coils, etc.). The "next state" to which the sequencer transitions is typically determined by the sequencer previous state. The time at which such a transition occurs is generally variable (since different NMR equipment "states" last for different durations within a typical NMR pulse sequence) and typically may also be determined by the previous state. Different microcode may by loaded into a control store (WCS) within the sequencer to define different pulse sequences.
Thus, MRI microcoded sequencers generally include a writable control store (WCS) containing a sequence of microinstructions that define a corresponding sequence of machine states. The microinstructions are, in one sense, a computer program executed by the sequencer. This microcode computer program specifies sequencer outputs (e.g., to control portions of the MRI system such as the RF transmitter, the gradient coils, etc.) and also specifies the duration of such sequencer outputs. In addition, the microcode specifies an ordered sequence of sequencer machine states--by providing a corresponding ordered "in line " sequence of microinstructions executed one after another (e.g., in the order in which the microinstructions are stored in the control store) and/or by providing conditional or unconditional "branching" microinstructions which cause particular microinstruction(s) to be performed in an order different from the order in which the microinstructions are stored in the control store.
Since the sequencer control store is writable (e.g., by a host computer linked to the sequencer), different NMR pulse sequences can be specified by simply downloading different microinstructions into the sequencer control store. Thus, different microinstruction sequences corresponding to hundreds of different NMR pulse sequences may be maintained on the host computer's mass storage (e.g., hard disk). Briefly, software executing on the host computer permits an operator to select (or create) particular sequencer microcode routines corresponding to particular experiments. The host computer then "links" and downloads the selected ("main") routines into the sequencer writable control store for execution by the sequencer. The host computer may download, along with the actual microcode routines, additional routines and data (e.g., commonly used subroutines, reference tables and the like) that must be present in the writable control store (and linked with the main routines) in order for the selected microcode routines to run.
U.S. Pat. No. 4,707,661 to Hoenninger, III et al (1987) (hereafter "Hoenninger '661") describes a highly successful technique for efficiently generating sequencer state change microinstructions. The entire disclosure (including the FIGURES) of Hoenninger '661 are hereby expressly incorporated herein by reference. The preferred embodiment Fast Linker disclosed and claimed in the subject application is an extension of the prior Linker design disclosed in Hoenninger '661. The following discussion briefly summarizes some (although not all) of the more important details disclosed in the Hoenninger '661 patent that relate to the arrangement disclosed and claimed in the subject application. The reader is referred to that prior Hoenninger '661 patent for additional details relating to that prior art microcode generation technique.
As is well known, the term "linker" or "link editor" as used in computer science typically refers to a program (or system) that resolves cross references (e.g., "external" references to "global" variables shared among several different programs and/or subroutines, address references permitting a one routine to call another routine, etc.) between routines (and subroutines) that have been assembled or compiled separately. A "linking loader" resolves such cross-references and loads the "linked" programs and subroutines into memory for execution. Although the microcode Linker/Loader described in the Hoenninger '661 patent resolves cross references, it performs many other tasks and functions (e.g., handling of external loop specifications and directives) that are generally non-analogous to non-MRI Linker functions.
Hoenninger '661 describes the use of program change tables (hereafter referred to as "PCTs") combined with techniques for grouping and replicating program segments with indexed symbolic addresses to greatly reduce the number of lines of microcode that must be written for a typical MRI sequence.
This earlier described technique relies upon a decomposition of MRI sequences into such program code "templates" (i.e., program segments) which encode the unique sequence of machine states required for only one set of spin echoes for one slice. The code templates are then logically associated with program change tables (PCTs) comprising lists of parameter values which may then be arbitrarily specified for any field in a line of microcode. This association permits a multiplicity of template implementations to be generated in a completely predictable way. Hoenninger '661 thus teaches that instead of generating each slice-specific portion of sequencer microcode independently, it is possible (due to the high degree of redundancy and similarity in MRI sequencer microcode from one program segment to the next) to replicate entire blocks of microcode based on a more general model or "template" of the microcode--and to merely replicate microcode program segments (with altered MRI parameter values and addresses as appropriate) to provide appropriate additional slice-specific program segments. Hoenninger '661 teaches embedding symbolic reference pointers within the template to refer to parameter values to be obtained externally from PCTs, but also recognizes that the parameter values themselves can be utilized and simply changed from one execution pass to the next.
The MRI Linker described in Hoenninger '661 accepts an "Linker Control Statement" as an input data string. The Hoenninger '661 patent describes the general format of such an input data string. This input data string is parsed to extract main routine and subroutine entries, and to ascertain table identifications and ranges corresponding to slice-specific entries. The microcode is generated in response to such Linker statements.
Slice-specific program segments cannot simply be re-executed for different slices because of the different parameters which vary from one slice to the next. Hoenninger '661 teaches replicating such slice-specific program segments by: (a) changing slice-specific parameter values as may be required for specific slices, and (b) appropriately indexing symbolic address arguments associated with "jump to subroutine" or "jump" instructions as well as the symbolic address(es) of the associated slice-specific program segments. Other program segments (e.g., those associated with sampling) are not replicated but are instead simply stored once at a predetermined place in memory and accessed (e.g., as a subroutine) by a fixed symbolic address at any point in the program.
During execution of the Linker program, any encountered subroutines that are not slice-specific are treated as true subroutines which are not replicated. On the other hand, all program segments designated as being "slice-specific" are replicated in a predetermined order (as specified by the input Linker Control Statement)--while indexing the corresponding symbolic addresses associated with the replicated program segments and also indexing the appropriate referenced PCT entries in a predetermined sequence so as to maintain proper correspondence between slice-specific main programs and subroutines in each replicated segment.
FIGS. 6A-6C of Hoenninger '661 illustrate exemplary "Linker" program control steps for generating microcode using the program change tables and templates mentioned above. These FIGURES are set forth herein as prior art FIGS. 1A-1C.
Briefly, after entering the Linker Program at 600 (where a "cycle" counter may be set to a content of "1"--this cycle counter keeping track of "phase encoding cycles" as will be understood by those skilled in this art), the slice-specific routines are expanded at 604 by (a) replicating slice-specific segments appearing within parentheses in an indicated order using indexed symbolic addresses and indexed parameters from the referenced PCTs (program change tables), and (b) not replicating subroutine segments not within the parentheses of the slice-dependent portion of the inputted linker control statement and also not indexing certain symbolic addresses associated with this subset of subroutines. In addition, the Linker of FIGS. 1A-1C expands slice-specific main program segments appearing within parentheses of the Linker Control Statement at 606 in a predetermined order (e.g., as specified by the syntax of the Linker Control Statement) using indexed symbolic addresses and indexed parameters from referenced PCTs (except for the predetermined subset of non-slice-specific subroutine segment references which are related as true and conventional subroutines without indexed symbolic addresses). Other program segments designated in the Linker Control Statement are also appropriately linked before the cycle counter is tested. Unless the last cycle has been linked, the cycle counter is incremented and the main program base memory location is updated and control is passed back to the beginning of routine 606. Once microcode for the last cycle of operation has been properly linked, the control is passed to block 614 where the final line of microcode is generated including a "stop" code, and an exit is taken from the Linker Program at block 616 (whereupon the generated microcode may be loaded and executed if desired).
The Linker described in the Hoenninger patent has (e.g., due to it high efficiency and speed) been highly successful in its own right. However, further improvements are possible. For example, it has become highly desirable to provide even more efficient and rapid linking of MRI sequence controller microcode than is provided by the Linker described in Hoenninger '661.
FIG. 1D describes an exemplary prior art sequencer microcode reloading technique used in the past in conjunction with the Liner described in Hoenninger '661. At block A (before the sequencer is started), the host computer links and loads the entire control store with micro-instructions (e.g., by performing the program control instructions shown in prior art FIGS. 1A-1C). When the sequencer is started (blocks B and C), the sequencer repetitively reads from the control store and executes the micro-instructions stored within the store--thus generating NMR pulse sequences for a desired NMR experiment. In more complex experiments the sequencer will reach the end of the control store before the experiment has terminated ("Y" exit of decision block C) and require micro-instructions that are not yet resident in the store. When the sequencer reaches the end of the control store, it suspends operations momentarily (block D) and requests the host to rewrite the control store. The host links an entire new sequencer control store-sized block of microcode (e.g., once again performing all of the instructions set forth in routine 606 shown in FIGS. 1A-1C, the symbol tables and PCTs generated by routine 604 preferably being retained by the host from before; block E) while the sequencer is executing the previously loaded microcode. It begins loading the sequencer memory as soon as it is requested to do so if linking has been completed, otherwise loading is delayed.
The sequencer can be designed so that the host can very rapidly load the writable control store (e.g., using direct memory access (DMA) techniques). Rewriting the control store at block E may thus introduce less than a one second delay if linking is completed when the sequencer requests reloading. Once the host has successfully rewritten the sequencer control store, the sequencer may resume operations at the beginning of the control store (or at some other predetermined transfer point) (block F). The writable control store can be reloaded as many times as necessary to cause the sequencer to execute the entire control program.
Unfortunately, this FIG. 1D technique generates some significant problems in the real time control context of an NMR sequencer. The regular RF stimulations provided during MRI imaging cause the NMR-sensitive molecules within the body being imaged to enter a dynamic steady state different from the unexcited steady state. If these regular stimulations are interrupted, relaxation causes the NMR-sensitive molecules to move away from the dynamic steady state toward their natural (unexcited) steady state. Interrupting the NMR pulse sequence to link microcode and reload the writable control store interrupts the regular stimulations.
A technique known as "spin conditioning" has been used to stimulate the body back to dynamic steady state after such an interruption (and before data acquisition resumes). However, spin conditioning wastes time and may also not be entirely effective in avoiding image degradation caused by the interruption. This is due to the fact that the exponential time constants of the spins in some human body tissues are 1-2 seconds and spin conditioning is not usually performed for the 5-10 seconds required to return to steady state. There may also be eddy currents in the magnet with time constants in excess of 1 second. Since the time between reloads of the control store is constant in most cases, the disruption is periodic and the Fourier Transform of the resulting data is sensitive to this periodic perturbation of the data, resulting in image artifacts. A disruption near the zero phase encoding data acquisition will cause especially strong effects. Interruption due to control store loading should be avoided in order to prevent loss of steady state in the body which can lead to artifacts and noise in the acquired image data-- and thus cause image degradation.
Copending, commonly-assigned application Ser. No. 07/571,258 of Zeilenga et al entitled "Continuously Loadable Microcode Store for MRI Control Sequencers" (attorney docket no. 89-108), now issued U.S. Pat. No. 5,144,242 describes an MRI pulse sequencer which permits microcode to be continually loaded substantially without interruption of MRI pulse sequences being generated by an associated MRI system--thus avoiding the image degradation and other problems resulting from interrupting the NMR pulse sequence to load microcode. However, the availability of a continually loadable MRI microcoded sequencer introduces speed and other requirements that may not be fully satisfied by the Linker described in the Hoenninger '661 patent.
It would be possible to use the Linker earlier described in the Hoenninger '661 patent to link and store (e.g., on mass storage) all of the required sequencer microcode ahead of time--and to then simply load the pre-generated microcode from memory and/or mass storage as required. Unfortunately, such an arrangement would require a great deal of latent processing time between user inputting of a "link and load" command and the actually beginning of sequencer execution. In order to increase overall MRI system throughput and flexibility, it would be highly desirable to drive such a continually loadable sequencer with a host processor that is capable of continually generating microcode "on the fly" for loading into the sequencer. Thus, it would be desirable for the host processor to be capable of rapidly linking and loading replacement pages of sequencer microcode in real time as needed, where the link time is always less than the execution time of a page of microcode. Through such cooperation between a continually loadable sequencer and a linker continually generating microcode, it would be possible to provide NMR pulse sequences of arbitrarily long duration without interruption--and without long startup latency.
One possible technique to accomplish such continual microcode linking is to execute the Linker of the type described in the Hoenninger '661 patent with a host processor that has sufficient processor resources dedicated to the linking function. However, relatively modest minicomputers are not capable of generating, linking and loading microcode at a sufficiently rapid rate to keep up with a continually loadable sequencer in the case of the fastest sequences.
It is also a design goal to eliminate the extra cost and added complexity of a dedicated linker processor. State-of-the-art MRI system design has moved towards a single processor architecture. In such a single processor architecture, a single main processor (e.g., a minicomputer) performs all data processing functions associated with data acquisition, reconstruction and display--as well as all data processing functions associated with microcode linking and loading (and other sequencer support). Unfortunately, data acquisition, reconstruction and display tasks are extremely processor intensive. The processor-intensive Linker described in the Hoenninger '661 patent cannot be efficiently, timely executed on a continual basis by a cost-effective host processor also engaged in simultaneous data acquisition and display (at least using current cost-effective minicomputer technology).
During the time the sequencer is operating, the host processor is busy acquiring data in real time (and generally also reconstructing and preferably displaying images). There are generally few processor resources left over for performing functions such as microcode linking. To be successful in such a host computer multitasking environment, a microcode linker/loader must place only minimal demands on the host processor during the time data is being acquired and/or displayed--while nevertheless still being capable of continually generating an arbitrary amount of microcode "on the fly" in real time so as to permit sequencer reloading while the sequencer is running.
The present invention provides an extremely fast and efficient microcode Linker that exerts minimal demands on the host processor once data acquisition has begun.
An important feature of the Fast Linker provided by the present invention is the use of memory image templates which can be efficiently constructed given the large amount of the microcode which is static from one signal generation process to the next. The collection of data for an MRI image is essentially the collection of an interference pattern which is generated by performing successive sequences of operations on the spin lattice in the object being imaged. Each sequence of operations is very similar to the previous one. This fact is exploited to create sequencer memory image templates which can be linked before loading simply by inserting (changing) the relatively few microcode field values in the instructions of the sequence which change from one signal generation process, or cycle, to the next. A cycle of microcode in the present invention typically may control the generation of all spin echo signals for all slices for a single phase encoding value.
Briefly, the Linker provided by the present invention generates an initial block ("template") of microcode in a more efficient manner in accordance with the steps shown in prior art FIGS. 1A-1C (and in the manner disclosed in the prior issued Hoenninger '661 patent). This initial block of microcode is stored in a memory buffer, and may be downloaded into the microcoded sequencer at an appropriate time. The Fast Linker provided by the present invention provides a highly efficient technique for deriving subsequent blocks of microcode by using the contents of the memory buffer as a template, by changing only those few values that need to be changed, and by reusing most of the template "as is" for reloading the sequencer memory.
The size of the microcode set for a cycle is determined by the number of instructions in the main routines of the sequence. Typically, the MRI control store is large enough to contain many cycles of microcode. A table is constructed at the time the microcode template is created in the load buffer which records the offsets of all instructions which have associated multi-entry cycle indexed program change table (PCT) values. When further code is to be linked and loaded, the only operation necessary before loading is to access the PCTs in a sequence data base based on the list in the table and to then insert the values so obtained into the appropriate instruction fields.
For example, to create a subsequent block of microcode, the initially-created microcode memory image may be edited to generate further microcode to be downloaded into the sequencer control store. Such "editing" does not need to edit addresses in the preferred embodiment--since in accordance with a further feature of the present invention, the edited image is written into the same area of the sequencer control store memory space the initially generated block was loaded into (and the addresses set forth in the microcode block may thus stay constant from one loading to the next). Rather, within the memory buffer only certain (e.g., phase encoding cycle-specific) values such as jump limits, clock times, gradient values are changed to generate a subsequent block of microcode.
Such limited editing of the existing microcode memory image can be performed extremely rapidly and efficiently by the host processor. The preferred embodiment provides efficient means (e.g., a tabular pointer and offset arrangement) to keep track of the information that must be changed to produce a subsequent page of microcode, and new values to be inserted into the memory image can be efficiently obtained from PCTs (program change tables) of the type described in the prior-issued Hoenninger '661 patent.
In the preferred embodiment, the microcode memory image may be continuously maintained in a host memory buffer and re-edited successive times (each time replacing the same limited set of old cycle-specific values with a new set of values) such that the host computer only needs to maintain a single copy of the microcode memory image for each memory page. Further efficiency is gained by repetitively editing the same microcode memory image in place and then downloading the edited memory image directly from the memory buffer to the sequencer (thus avoiding copying from one memory buffer to another and avoiding copying between mass storage and memory).
Continual linking and loading of the sequencer microcode control store when the sequencer is running ensures that the sequencer outputs are not interrupted even though the control store is not large enough to store all of the microcode needed to execute an MRI sequence. The Fast Linker provided by the present invention is capable of continually loading a sequencer writable control store and is fast enough to run under a time shared operating system at the same time a higher priority data acquisition and display process is executing. The preferred embodiment Fast Linker is (as one example) quick enough on the MicroVAX II (about 100 ms per 1024 lines of microcode linked when running as the sole process) that it does not have to run as a "time critical" process (which greatly improves the performance and responsiveness of the overall MRI system). This speed also allows fast continuous sequences which generate, reconstruct and display an image periodically (e.g., every 1 sec) for long periods of time to run successfully on a MicroVAX II (which provides a relatively modest CPU throughput less than 1 Mips).